import java.util.HashMap;
import java.util.Map;
 // 力扣92. 反转链表 II
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right){
            return head;
        }
        Map<Integer,ListNode> map = new HashMap<>();
        ListNode cur = head;
        int k = 1;
        while(cur!=null){ // 将要反转的结点存在哈希表,用key表示第k个节点
            if(left<=k && k<=right){
                ListNode newN = new ListNode(cur.val);
                map.put(k,newN);
            }
            if(k>right){
                break;
            }
            k++;
            cur = cur.next;
        }

        cur = head;
        ListNode prev = null;
        k = 1;
        while(cur!=null){ // 反转第 left 到第 right 个的结点
            if(left<=k && k<=right){
                map.get(k).next = prev;
                prev = map.get(k);
            }
            if(k>right){
                break;
            }
            cur = cur.next;
            k++;
        }

        map.get(left).next = cur; // 将第 right 个节点以后的结点接上
        if(left>1){ // 将 left 前面的结点接上 反转后的头节点
            cur = head;
            for(int i = 1; i<left-1 ;i++){
                cur = cur.next;
            }
            cur.next = map.get(right);
            return head;
        }else{ // left 为1就说明是从头节点开始反转，所以直接返回 map.get(right);
            return map.get(right);
        }
    }
}





// 力扣82. 删除排序链表中的重复元素 II
class Solution1 {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1); // 虚拟头节点
        ListNode tail = dummy; // 结果链表的尾部

        ListNode prev = head;
        ListNode cur = head.next;

        while (cur != null) {
            if (prev.val != cur.val) {
                tail.next = prev; // 直接连接原节点，无需新建
                tail = tail.next;
                prev = cur;
                cur = cur.next;
            } else {
                // 跳过所有重复节点
                while (cur != null && cur.val == prev.val) {
                    cur = cur.next;
                }
                prev = cur; // prev 移动到下一个非重复节点
                if (cur != null) {
                    cur = cur.next;
                }
            }
        }

        // 处理最后一个节点
        if (prev != null) {
            tail.next = prev;
            tail = tail.next;
        }
        tail.next = null; // 确保结果链表正确终止

        return dummy.next;
    }
}